{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Cracking the Safe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #graph #eulerian-circuit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #图 #欧拉回路"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: crackSafe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #破解保险箱"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一个需要密码才能打开的保险箱。密码是&nbsp;<code>n</code> 位数, 密码的每一位都是范围&nbsp;<code>[0, k - 1]</code>&nbsp;中的一个数字。</p>\n",
    "\n",
    "<p>保险箱有一种特殊的密码校验方法，你可以随意输入密码序列，保险箱会自动记住 <strong>最后&nbsp;<code>n</code>&nbsp;位输入</strong> ，如果匹配，则能够打开保险箱。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，正确的密码是 <code>\"345\"</code> ，并且你输入的是 <code>\"012345\"</code> ：\n",
    "\n",
    "\t<ul>\n",
    "\t\t<li>输入 <code>0</code> 之后，最后 <code>3</code> 位输入是 <code>\"0\"</code> ，不正确。</li>\n",
    "\t\t<li>输入 <code>1</code> 之后，最后 <code>3</code> 位输入是 <code>\"01\"</code> ，不正确。</li>\n",
    "\t\t<li>输入 <code>2</code> 之后，最后 <code>3</code> 位输入是 <code>\"012\"</code> ，不正确。</li>\n",
    "\t\t<li>输入 <code>3</code> 之后，最后 <code>3</code> 位输入是 <code>\"123\"</code> ，不正确。</li>\n",
    "\t\t<li>输入 <code>4</code> 之后，最后 <code>3</code> 位输入是 <code>\"234\"</code> ，不正确。</li>\n",
    "\t\t<li>输入 <code>5</code> 之后，最后 <code>3</code> 位输入是 <code>\"345\"</code> ，正确，打开保险箱。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>在只知道密码位数 <code>n</code> 和范围边界 <code>k</code> 的前提下，请你找出并返回确保在输入的 <strong>某个时刻</strong> 能够打开保险箱的任一 <strong>最短</strong> 密码序列 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1, k = 2\n",
    "<strong>输出：</strong>\"10\"\n",
    "<strong>解释：</strong>密码只有 1 位，所以输入每一位就可以。\"01\" 也能够确保打开保险箱。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2, k = 2\n",
    "<strong>输出：</strong>\"01100\"\n",
    "<strong>解释：</strong>对于每种可能的密码：\n",
    "- \"00\" 从第 4 位开始输入。\n",
    "- \"01\" 从第 1 位开始输入。\n",
    "- \"10\" 从第 3 位开始输入。\n",
    "- \"11\" 从第 2 位开始输入。\n",
    "因此 \"01100\" 可以确保打开保险箱。\"01100\"、\"10011\" 和 \"11001\" 也可以确保打开保险箱。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 4</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 10</code></li>\n",
    "\t<li><code>1 &lt;= k<sup>n</sup> &lt;= 4096</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [cracking-the-safe](https://leetcode.cn/problems/cracking-the-safe/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [cracking-the-safe](https://leetcode.cn/problems/cracking-the-safe/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1\\n2', '2\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        kn = k ** n  # 可能的密码总数\n",
    "        kn_1 = k ** (n - 1)  # 前n-1位的密码总数\n",
    "        num = [k - 1] * kn_1  # 初始化每个位置的数字为k-1\n",
    "        s = ['0'] * (kn + (n - 1))  # 初始化密码列表为n个'0'\n",
    "        node = 0  # 节点初始值为0\n",
    "        for i in range(n - 1, len(s)):\n",
    "            s[i] = str(num[node])  # 将当前节点对应的数字赋值给密码列表的当前位置\n",
    "            num[node] -= 1  # 将当前节点对应的数字减1\n",
    "            node = node * k - int(s[i - (n - 1)]) * kn_1 + num[node] + 1  # 更新节点的值\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        if n == 1:\n",
    "            ans = '0123456789'\n",
    "            return ans[:k]\n",
    "        ans = '0'*n\n",
    "        set1 = set([ans])\n",
    "        for _ in range(k**n-1):\n",
    "            for i in list(range(k))[::-1]:\n",
    "                code = ans[-n+1:]+str(i)\n",
    "                if code not in set1:\n",
    "                    ans += str(i)\n",
    "                    set1.add(code)\n",
    "                    break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from collections import deque\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        dq = deque(['0' * n])\n",
    "        used = set(['0' * n])\n",
    "        ans = '0' * n\n",
    "        while dq:\n",
    "            pw = dq.popleft()\n",
    "            for i in range(k - 1, -1, -1):\n",
    "                npw = pw[1:] + str(i)\n",
    "                if npw in used:\n",
    "                    continue\n",
    "                dq.append(npw)\n",
    "                used.add(npw)\n",
    "                ans += str(i)\n",
    "                break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        ans=''\n",
    "        if n==1:\n",
    "            for i in range(k):\n",
    "                ans+=str(i)\n",
    "            return ans\n",
    "        pailie=set()\n",
    "        temp=(n-1)*'0'+str(k-1)\n",
    "        pailie.add(temp)\n",
    "        ans+=temp\n",
    "        for i in range(pow(k,n)-1):\n",
    "            new=k-1\n",
    "            temp=ans[-(n-1):]+str(new)\n",
    "            while temp in pailie:\n",
    "                new-=1\n",
    "                temp=ans[-(n-1):]+str(new)\n",
    "            pailie.add(temp)\n",
    "            ans+=str(new)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from collections import deque\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        dq = deque(['0' * n])\n",
    "        used = set(['0' * n])\n",
    "        ans = '0' * n\n",
    "        while dq:\n",
    "            pw = dq.popleft()\n",
    "            for i in range(k - 1, -1, -1):\n",
    "                npw = pw[1:] + str(i)\n",
    "                if npw in used:\n",
    "                    continue\n",
    "                used.add(npw)\n",
    "                dq.append(npw)\n",
    "                ans += str(i)\n",
    "                break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        # 特判:\n",
    "        if n == 1:\n",
    "            return ''.join([str(i) for i in range(k)])\n",
    "        if k == 1:\n",
    "            return '0'*n\n",
    "        \n",
    "        # 建图\n",
    "        graph = [[x for x in range(k-1,-1,-1)] for _ in range(k**(n-1))]\n",
    "\n",
    "        # Hierholzer 求欧拉路径\n",
    "        ans = []\n",
    "        def dfs(cur):\n",
    "            while len(graph[cur]):\n",
    "                x = graph[cur].pop()\n",
    "                nxt = (cur * k + x) % (k**(n-1))\n",
    "                dfs(nxt)\n",
    "                ans.append(x)\n",
    "        dfs(0)\n",
    "        return ''.join([str(i) for i in ans]) + '0'*(n-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        seen = set()\n",
    "        ans = list()\n",
    "        highest = 10 ** (n - 1)\n",
    "        def dfs(node:int):\n",
    "            for x in range(k):\n",
    "                nei = node * 10 + x\n",
    "                if nei not in seen:\n",
    "                    seen.add(nei)\n",
    "                    dfs(nei % highest)\n",
    "                    ans.append(str(x))\n",
    "        \n",
    "        dfs(0)\n",
    "        return \"\".join(ans) + \"0\" *(n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# File       : Q753.py\n",
    "# Time       ：2023/9/20 15:11\n",
    "# Author     ：author name\n",
    "# version    ：python 3\n",
    "# Description：\n",
    "\"\"\"\n",
    "\n",
    "\"\"\"\n",
    "753. 破解保险箱\n",
    "提示\n",
    "困难\n",
    "238\n",
    "相关企业\n",
    "有一个需要密码才能打开的保险箱。密码是 n 位数, 密码的每一位都是范围 [0, k - 1] 中的一个数字。\n",
    "\n",
    "保险箱有一种特殊的密码校验方法，你可以随意输入密码序列，保险箱会自动记住 最后 n 位输入 ，如果匹配，则能够打开保险箱。\n",
    "\n",
    "例如，正确的密码是 \"345\" ，并且你输入的是 \"012345\" ：\n",
    "输入 0 之后，最后 3 位输入是 \"0\" ，不正确。\n",
    "输入 1 之后，最后 3 位输入是 \"01\" ，不正确。\n",
    "输入 2 之后，最后 3 位输入是 \"012\" ，不正确。\n",
    "输入 3 之后，最后 3 位输入是 \"123\" ，不正确。\n",
    "输入 4 之后，最后 3 位输入是 \"234\" ，不正确。\n",
    "输入 5 之后，最后 3 位输入是 \"345\" ，正确，打开保险箱。\n",
    "在只知道密码位数 n 和范围边界 k 的前提下，请你找出并返回确保在输入的 某个时刻 能够打开保险箱的任一 最短 密码序列 。\n",
    "\n",
    " \n",
    "\n",
    "示例 1：\n",
    "\n",
    "输入：n = 1, k = 2\n",
    "输出：\"10\"\n",
    "解释：密码只有 1 位，所以输入每一位就可以。\"01\" 也能够确保打开保险箱。\n",
    "示例 2：\n",
    "\n",
    "输入：n = 2, k = 2\n",
    "输出：\"01100\"\n",
    "解释：对于每种可能的密码：\n",
    "- \"00\" 从第 4 位开始输入。\n",
    "- \"01\" 从第 1 位开始输入。\n",
    "- \"10\" 从第 3 位开始输入。\n",
    "- \"11\" 从第 2 位开始输入。\n",
    "因此 \"01100\" 可以确保打开保险箱。\"01100\"、\"10011\" 和 \"11001\" 也可以确保打开保险箱。\n",
    " \n",
    "\n",
    "提示：\n",
    "\n",
    "1 <= n <= 4\n",
    "1 <= k <= 10\n",
    "1 <= kn <= 4096\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        max_v = 10 ** (n - 1)\n",
    "        def dfs(node):\n",
    "            for t in range(k):\n",
    "                tmp = node * 10 + t\n",
    "                if tmp not in seen:\n",
    "                    seen.add(tmp)\n",
    "                    tmp = tmp % max_v\n",
    "                    dfs(tmp)\n",
    "                    res.append(str(t))\n",
    "\n",
    "        seen = set()\n",
    "        res = list()\n",
    "        dfs(0)\n",
    "        return \"\".join(res) + \"0\" * (n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        seen = set()\n",
    "        ans = list()\n",
    "        highest = 10 ** (n - 1)\n",
    "\n",
    "        def dfs(node: int):\n",
    "            for x in range(k):\n",
    "                nei = node * 10 + x\n",
    "                if nei not in seen:\n",
    "                    seen.add(nei)\n",
    "                    dfs(nei % highest)\n",
    "                    ans.append(str(x))\n",
    "\n",
    "        dfs(0)\n",
    "        return \"\".join(ans) + \"0\" * (n - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        seen = set()\n",
    "        ans = list()\n",
    "        highest = 10 ** (n - 1)\n",
    "\n",
    "        def dfs(node: int):\n",
    "            for x in range(k):\n",
    "                nei = node * 10 + x\n",
    "                if nei not in seen:\n",
    "                    seen.add(nei)\n",
    "                    dfs(nei % highest)\n",
    "                    ans.append(str(x))\n",
    "\n",
    "        dfs(0)\n",
    "        return \"\".join(ans) + \"0\" * (n - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        ans = ''\n",
    "        Mod = 10 ** (n-1) \n",
    "        vis = set() \n",
    "        def dfs(root):\n",
    "            nonlocal ans \n",
    "            for i in range(k):\n",
    "                nxt = root * 10 + i \n",
    "                if nxt not in vis:\n",
    "                    vis.add(nxt) \n",
    "                    dfs(nxt%Mod) \n",
    "                    ans+=str(i) \n",
    "        dfs(0)\n",
    "        return ans + '0'*(n-1) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = \"\"\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "\n",
    "        seen = set()\n",
    "\n",
    "        hlp = 10 ** (n - 1) ##用于保证保存数组永远是n位的\n",
    "\n",
    "        ans = list()\n",
    "\n",
    "        def dfs(node):\n",
    "            for x in range(k):\n",
    "                tmp = node * 10 + x\n",
    "                if tmp not in seen:\n",
    "                    seen.add(tmp)\n",
    "                    dfs(tmp % hlp)\n",
    "                    self.ans += str(x)\n",
    "        dfs(0)\n",
    "        return (self.ans + \"0\" * (n - 1))\n",
    "\n",
    "\n",
    "        # def dfs(node: int):\n",
    "        #     for x in range(k):\n",
    "        #         nei = node * 10 + x\n",
    "        #         if nei not in seen:\n",
    "        #             seen.add(nei)\n",
    "        #             dfs(nei % hlp)\n",
    "        #             ans.append(str(x))\n",
    "        #             self.ans += (str(x))\n",
    "\n",
    "        #dfs(0)\n",
    "        #print(self.ans)\n",
    "        #return \"\".join(ans) + \"0\" * (n - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        visited = set()\n",
    "        ans = list()\n",
    "        highest = 10 ** (n - 1)\n",
    "\n",
    "        def dfs(node: int):\n",
    "            for x in range(k):\n",
    "                nei = node * 10 + x\n",
    "                if nei not in visited:\n",
    "                    visited.add(nei)\n",
    "                    dfs(nei % highest)\n",
    "                    ans.append(str(x))\n",
    "\n",
    "        dfs(0)\n",
    "        return ''.join(ans) + '0' * (n - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, n: int, k: int, node: int, visit:set, answer:list)->None:\n",
    "        highest = 10 ** (n - 1)\n",
    "        for x in range(k):\n",
    "            neighbor = node * 10 + x\n",
    "            if neighbor not in visit:\n",
    "                visit.add(neighbor)\n",
    "                self.dfs(n,k,neighbor % highest,visit,answer)\n",
    "                answer.append(str(x))\n",
    "\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        retVal = \"\"\n",
    "\n",
    "        visit = set()\n",
    "        answer = list()\n",
    "        self.dfs(n,k,0,visit,answer)\n",
    "        retVal = \"\".join(answer) + \"0\" * (n - 1)\n",
    "\n",
    "        return retVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        def dfs(u):\n",
    "            for x in range(k):\n",
    "                e = u * 10 + x\n",
    "                if e not in vis:\n",
    "                    vis.add(e)\n",
    "                    v = e % mod\n",
    "                    dfs(v)\n",
    "                    ans.append(str(x))\n",
    "                    # print(ans)\n",
    "\n",
    "        mod = 10 ** (n - 1)\n",
    "        vis = set()\n",
    "        ans = []\n",
    "        dfs(0)\n",
    "        ans.append(\"0\" * (n - 1))\n",
    "        return \"\".join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        # 初始化一个集合，用来存储已经出现过的密码\n",
    "        seen = set()\n",
    "        # 初始化一个列表，用来存储构造的字符串\n",
    "        ans = list()\n",
    "        # 计算最高位的权值，用来计算密码的数值\n",
    "        highest = 10 ** (n - 1)\n",
    "\n",
    "        # 定义一个深度优先搜索的函数\n",
    "        def dfs(node: int):\n",
    "            # 遍历从0到k-1的所有数字\n",
    "            for x in range(k):\n",
    "                # 计算新的密码的数值\n",
    "                nei = node * 10 + x\n",
    "                # 如果新的密码不在集合中\n",
    "                if nei not in seen:\n",
    "                    # 把新的密码加入到集合中\n",
    "                    seen.add(nei)\n",
    "                    # 递归地调用深度优先搜索，去掉最高位的数字\n",
    "                    dfs(nei % highest)\n",
    "                    # 把数字转换成字符串，加入到列表中\n",
    "                    ans.append(str(x))\n",
    "\n",
    "        # 从0开始进行深度优先搜索\n",
    "        dfs(0)\n",
    "        # 返回构造的字符串，补上最后的n-1个0\n",
    "        return \"\".join(ans) +\"0\" * (n - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = \"\"\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "\n",
    "        seen = set()\n",
    "\n",
    "        hlp = 10 ** (n - 1) ##用于保证保存数组永远是n位的\n",
    "\n",
    "        ans = list()\n",
    "\n",
    "        def dfs(node):\n",
    "            for x in range(k):\n",
    "                tmp = node * 10 + x\n",
    "                if tmp not in seen:\n",
    "                    seen.add(tmp)\n",
    "                    dfs(tmp % hlp)\n",
    "                    self.ans += str(x)\n",
    "        dfs(0)\n",
    "        return (self.ans + \"0\" * (n - 1))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        seen = set()\n",
    "        ans = list()\n",
    "        highest = 10 ** (n - 1)\n",
    "\n",
    "        def dfs(node: int):\n",
    "            for x in range(k):\n",
    "                nei = node * 10 + x\n",
    "                if nei not in seen:\n",
    "                    seen.add(nei)\n",
    "                    dfs(nei % highest)\n",
    "                    ans.append(str(x))\n",
    "\n",
    "        dfs(0)\n",
    "        return \"\".join(ans) + \"0\" * (n - 1)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        seen=set()\n",
    "        stack=[]\n",
    "        highest=10**(n-1)\n",
    "        def dfs(node):\n",
    "            for x in range(k):\n",
    "                ne=node*10+x\n",
    "                if ne not in seen:\n",
    "                    seen.add(ne)\n",
    "                    dfs(ne%highest)\n",
    "                    stack.append(str(x))\n",
    "        dfs(0)\n",
    "        return ''.join(stack)+'0'*(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def find(k,node,num_dict,res):\n",
    "    for i in range(k):\n",
    "        new_node = node+str(i)\n",
    "        if new_node not in num_dict.keys():\n",
    "            num_dict[new_node] = True\n",
    "            new_node = new_node[1:]\n",
    "            find(k,new_node,num_dict,res)\n",
    "            res[0]+=str(i)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        num_dict = {}\n",
    "        node = \"\"\n",
    "        for i in range(n-1):\n",
    "            node+=\"0\"\n",
    "        res = [\"\"]\n",
    "        find(k,node,num_dict,res)\n",
    "        for i in range(n-1):\n",
    "            res[0] += \"0\"\n",
    "        return res[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        seen = set()\n",
    "        ans = list()\n",
    "        highest = 10 ** (n - 1)\n",
    "\n",
    "        def dfs(node: int):\n",
    "            for x in range(k):\n",
    "                nei = node * 10 + x\n",
    "                if nei not in seen:\n",
    "                    seen.add(nei)\n",
    "                    dfs(nei % highest)\n",
    "                    ans.append(str(x))\n",
    "\n",
    "        dfs(0)\n",
    "        return \"\".join(ans) + \"0\" * (n - 1)\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/cracking-the-safe/solutions/393529/po-jie-bao-xian-xiang-by-leetcode-solution/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def crackSafe(self, n: int, k: int) -> str:\r\n",
    "        seen = set()\r\n",
    "        ans = list()\r\n",
    "        highest = 10 ** (n - 1)\r\n",
    "\r\n",
    "        def dfs(node: int):\r\n",
    "            for x in range(k):\r\n",
    "                nei = node * 10 + x\r\n",
    "                if nei not in seen:\r\n",
    "                    seen.add(nei)\r\n",
    "                    dfs(nei % highest)\r\n",
    "                    ans.append(str(x))\r\n",
    "\r\n",
    "        dfs(0)\r\n",
    "        return \"\".join(ans) + \"0\" * (n - 1)\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        seen = set()\n",
    "        ans = list()\n",
    "        highest = 10 ** (n - 1)\n",
    "\n",
    "        def dfs(node: int):\n",
    "            for x in range(k):\n",
    "                nei = node * 10 + x\n",
    "                if nei not in seen:\n",
    "                    seen.add(nei)\n",
    "                    dfs(nei % highest)\n",
    "                    ans.append(str(x))\n",
    "\n",
    "        dfs(0)\n",
    "        return \"\".join(ans) + \"0\" * (n - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        seen = set()\n",
    "        ans = list()\n",
    "        highest = 10 ** (n - 1)\n",
    "\n",
    "        def dfs(node: int):\n",
    "            for x in range(k):\n",
    "                nei = node * 10 + x\n",
    "                if nei not in seen:\n",
    "                    seen.add(nei)\n",
    "                    dfs(nei % highest)\n",
    "                    ans.append(str(x))\n",
    "\n",
    "        dfs(0)\n",
    "        return \"\".join(ans) + \"0\" * (n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        MAX = 10 ** (n - 1)\n",
    "        def dfs(node):\n",
    "            for x in range(k):\n",
    "                cur = node * 10 + x\n",
    "                if cur not in seen:\n",
    "                    seen.add(cur)\n",
    "                    cur = cur % MAX\n",
    "                    dfs(cur)\n",
    "                    res.append(str(x))\n",
    "\n",
    "        res = []\n",
    "        seen = set()\n",
    "        dfs(0)\n",
    "        return \"\".join(res) + \"0\" * (n - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        # 构建有向图\n",
    "        def dfs(u):\n",
    "            for x in range(k):\n",
    "                e = u * 10 + x\n",
    "                if e not in vis:\n",
    "                    vis.add(e)\n",
    "                    v = e % mod\n",
    "                    dfs(v)\n",
    "                    ans.append(str(x))\n",
    "        # 开方\n",
    "        mod = 10 ** (n - 1)\n",
    "        vis = set()\n",
    "        ans = []\n",
    "        dfs(0)\n",
    "        ans.append(\"0\" * (n - 1))\n",
    "        return \"\".join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def crackSafe(self, n, k):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :type k: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        s = set()\n",
    "        start = \"0\" * (n - 1)\n",
    "        ans = \"\"\n",
    "\n",
    "        def dfs(cur, num):\n",
    "            nonlocal ans\n",
    "            for i in range(num):\n",
    "                newstr = cur + str(i)\n",
    "                if not s.__contains__(newstr):\n",
    "                    s.add(newstr)\n",
    "                    nextstr = newstr[1:]\n",
    "                    dfs(nextstr, num)\n",
    "                    ans += str(i)\n",
    "\n",
    "        dfs(start, k)\n",
    "        ans += start\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def find(k,node,num_dict,res):\n",
    "    for i in range(k):\n",
    "        new_node = node+str(i)\n",
    "        if new_node not in num_dict.keys():\n",
    "            num_dict[new_node] = True\n",
    "            new_node = new_node[1:]\n",
    "            find(k,new_node,num_dict,res)\n",
    "            res[0]+=str(i)\n",
    "\n",
    "def find1(k,node,num_dict,res,res2):\n",
    "    for i in range(k):\n",
    "        new_node = node+str(i)\n",
    "        if new_node not in num_dict.keys():\n",
    "            num_dict[new_node] = True\n",
    "            new_node = new_node[1:]\n",
    "            res.append(str(i))\n",
    "            find1(k,new_node,num_dict,res,res2)\n",
    "            res2.append(res.pop())\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        # num_dict = {}\n",
    "        # node = \"\"\n",
    "        # for i in range(n-1):\n",
    "        #     node+=\"0\"\n",
    "        # res = [\"\"]\n",
    "        # find(k,node,num_dict,res)\n",
    "        # for i in range(n-1):\n",
    "        #     res[0] += \"0\"\n",
    "        # return res[0]\n",
    "        num_dict = {}\n",
    "        node = \"\"\n",
    "        for i in range(n-1):\n",
    "            node+=\"0\"\n",
    "        res = [node]\n",
    "        res2 = []\n",
    "        find1(k,node,num_dict,res,res2)\n",
    "        res_str = \"\"\n",
    "        for i in res:\n",
    "            res_str+=i\n",
    "        for i in range(len(res2)-1,-1,-1):\n",
    "            res_str+=res2[i]\n",
    "        return res_str\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        vis= set()\n",
    "        ans = []\n",
    "        def dfs(arr):\n",
    "            for i in range(k):\n",
    "                a=arr+str(i)\n",
    "                if a in vis:\n",
    "                    continue\n",
    "                else:\n",
    "                    vis.add(a)\n",
    "                    tmp=a[1:]\n",
    "                    dfs(tmp)\n",
    "                    ans.append(str(i))\n",
    "           \n",
    "        x=\"0\"*(n-1)\n",
    "        dfs(x)\n",
    "      \n",
    "        return \"\".join(ans)+\"0\"*(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        visited = set()\n",
    "        ans = []\n",
    "\n",
    "        def dfs(node):\n",
    "            for i in range(k):\n",
    "                edge = node + str(i)\n",
    "                if edge in visited:\n",
    "                    continue\n",
    "                else:\n",
    "                    visited.add(edge)\n",
    "                    dfs(edge[1::])\n",
    "                    ans.append(str(i))\n",
    "\n",
    "        dfs(\"0\" * (n-1))\n",
    "        return \"\".join(ans) + \"0\" * (n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        vis = set()\n",
    "        ans = []\n",
    "\n",
    "        def dfs(s):\n",
    "            for x in range(k):\n",
    "                t = s + str(x)\n",
    "                if t not in vis:\n",
    "                    vis.add(t)\n",
    "                    dfs(t[1:])\n",
    "                    ans.append(str(x))\n",
    "        \n",
    "        dfs('0'*(n - 1))\n",
    "        return ''.join(ans) + '0'*(n - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        cpwd=k**n\n",
    "        tries=cpwd-1+n\n",
    "        s=set()\n",
    "        path=[]\n",
    "        def dfs(index):\n",
    "#            判断状态是否满足？\n",
    "#            状态：遍历的长度，所有子串都已包含\n",
    "#                当遍历到最短长度时：\n",
    "#                    如果所有情况都已包含，则说明找到答案\n",
    "#                    否则，说明这一条路到底也没有正确答案，向上返回\n",
    "            if index==tries:\n",
    "                if len(s)==cpwd:\n",
    "                    return True\n",
    "                return False\n",
    "            #当还未到底时，进行操作处理：\n",
    "            #每一位都是k个数可选\n",
    "            for i in range(k):\n",
    "                #选择一个数\n",
    "                path.append(str(i))\n",
    "                pwd=''\n",
    "                if len(path)>=n:\n",
    "                    #获取一个新子串\n",
    "                    pwd=''.join(path[len(path)-n:len(path)])\n",
    "                    #剪枝：\n",
    "                    #如果子串是重复的，已存在，则，丢弃，不再向下搜索。重新横向选择下一个数\n",
    "                    if pwd in s:\n",
    "                        path.pop()\n",
    "                        continue\n",
    "                    #如果是新子串，加入set中\n",
    "                    s.add(pwd)\n",
    "                #继续纵向搜索\n",
    "                if dfs(index+1):\n",
    "                    return True\n",
    "                path.pop()\n",
    "                if pwd!='':\n",
    "                    s.remove(pwd)\n",
    "        dfs(0)\n",
    "        return ''.join(path)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        cpwd=k**n\n",
    "        tries=cpwd-1+n\n",
    "        s=set()\n",
    "        path=[]\n",
    "        d=defaultdict(int)\n",
    "        def dfs(index):\n",
    "            if index==tries:\n",
    "                if len(s)==cpwd:\n",
    "                    return True\n",
    "                return False\n",
    "            for i in range(k):\n",
    "                path.append(str(i))\n",
    "                pwd=''\n",
    "                if len(path)>=n:\n",
    "                    pwd=''.join(path[len(path)-n:len(path)])\n",
    "                    if pwd in s:\n",
    "                        path.pop()\n",
    "                        continue\n",
    "                    s.add(pwd)\n",
    "                    d[pwd]+=1\n",
    "                if dfs(index+1):\n",
    "                    return True\n",
    "                path.pop()\n",
    "                if pwd!='':\n",
    "                    d[pwd]-=1\n",
    "                    if d[pwd]==0:\n",
    "                        s.remove(pwd)\n",
    "        dfs(0)\n",
    "        return ''.join(path)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        s=set()\n",
    "        ls=[\"0\"]*(n-1)\n",
    "        def dfs(last):\n",
    "            for i in range(k-1,-1,-1):\n",
    "                now=last+str(i)\n",
    "                #print(now,k)\n",
    "                if now not in s:\n",
    "                    s.add(now)\n",
    "                    ls.append(str(i))\n",
    "                    dfs(now[1:])\n",
    "                    return \n",
    "        dfs(\"0\"*(n-1))\n",
    "        return \"\".join(ls)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        global path\n",
    "        path = []\n",
    "        st = [False for _ in range(10 ** (n+ 1))]\n",
    "        def dfs(v: int):\n",
    "            u = str(v)\n",
    "            while len(u) < n:\n",
    "                u = '0' + u\n",
    "            u = u[1:]\n",
    "            for i in range(k):\n",
    "                ne = int(u + str(i))\n",
    "                if st[ne]:\n",
    "                    continue\n",
    "                st[ne] = True\n",
    "                dfs(ne)\n",
    "                global path\n",
    "                path.append(str(i))\n",
    "        dfs(0)\n",
    "        for i in range(n - 1):\n",
    "            path.append('0')\n",
    "        return \"\".join(path)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        # 显然需要含有所有n位的结果\n",
    "        # 首先需要分析出n的有什么含义,n其实表示了每个状态的位数\n",
    "        # 比如 n == 2, k==2，就会有01、10，00，11四种状态 k**n种\n",
    "        # 每种状态有k个连接，有向图来的，出入度一样，比存在欧拉回路\n",
    "        g = defaultdict(list)\n",
    "        def f(s):\n",
    "            if len(s) == n:\n",
    "                for i in range(k):\n",
    "                    s1 = s[1:] + str(i)\n",
    "                    if s != s1:\n",
    "                        g[s].append(s1)\n",
    "                return\n",
    "            for i in range(k):\n",
    "                f(s + str(i))\n",
    "        \n",
    "        f('')\n",
    "\n",
    "        def dfs(x):\n",
    "            vis.add(x)\n",
    "            while g[x]:\n",
    "                node = g[x].pop()\n",
    "                if node not in vis:\n",
    "                    dfs(node)\n",
    "            ans.append(x[-1])\n",
    "        \n",
    "        ans = []\n",
    "        vis = set()\n",
    "        dfs('0'*n)\n",
    "        return ''.join(ans) + '0' * (n-1)\n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        total = pow(k,n)\n",
    "        self.ans = \"\"\n",
    "        ###注意0*n一定存在而且是初始位置！！！！因此以此为起点\n",
    "        ##这一部分一定要深入理解题意才能进行求解！！！\n",
    "        for i in range(n):\n",
    "            self.ans += \"0\"\n",
    "        #print(ans)\n",
    "        \n",
    "        visit = set()\n",
    "        visit.add(self.ans)\n",
    "        \n",
    "        def dfs(ans: str, visit: set) -> bool:\n",
    "            ###注意看好是判断哪个长度！！！这里是判断visit长度而非ans长度！！！\n",
    "            if len(visit) == total:\n",
    "                return True\n",
    "            ###注意C++中的substr()相关语法!!!\n",
    "            node = self.ans[len(self.ans)-(n-1) : len(self.ans)]\n",
    "            #print(node)\n",
    "            for c in range(0,k):\n",
    "                node = node + str(c)\n",
    "                #print(node)\n",
    "                if node not in visit:\n",
    "                    visit.add(node)\n",
    "                    #print(visit)\n",
    "                    self.ans = self.ans + str(c)\n",
    "                    #print(self.ans)\n",
    "                    if dfs(self.ans,visit):\n",
    "                        return True\n",
    "                    self.ans = self.ans[:-1]\n",
    "                    #print(self.ans)\n",
    "                    ###注意python中set怎样去除元素\n",
    "                    visit.remove(node)\n",
    "                node = node[:-1]\n",
    "            return False\n",
    "\n",
    "        if dfs(self.ans,visit):\n",
    "            return self.ans\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        if n == 1:\n",
    "            return \"\".join([str(i) for i in range(k)])\n",
    "        S = set()\n",
    "        m = k ** n + n - 1\n",
    "        ans = \"\"\n",
    "        def dfs(a):\n",
    "            nonlocal ans\n",
    "            if len(a) == m:\n",
    "                ans = a\n",
    "                return \n",
    "            o = a[1-n:]\n",
    "            for i in range(k):\n",
    "                s = o + str(i)\n",
    "                if s not in S:\n",
    "                    S.add(s)\n",
    "                    dfs(a + str(i))\n",
    "                    S.remove(s)\n",
    "                    if ans:\n",
    "                        return \n",
    "        dfs(\"\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "        visit = set()\n",
    "        res = list()\n",
    "        def dfs(cur):\n",
    "            for i in range(k):\n",
    "                tmp = cur + str(i)\n",
    "                if tmp[-n:] not in visit:\n",
    "                    for j in range(1, n+1):\n",
    "                        visit.add(tmp[-j:])\n",
    "                    dfs(tmp)\n",
    "                    res.append(str(i))\n",
    "                    # print(tmp, visit, res)\n",
    "        \n",
    "        dfs(\"\")\n",
    "        return \"\".join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackSafe(self, n: int, k: int) -> str:\n",
    "\n",
    "\n",
    "        ops = [str(x) for x in range(k)]\n",
    "        if n == 1:\n",
    "            return \"\".join(ops)\n",
    "\n",
    "        # 套圈 [0,k-1]\n",
    "        euler = \"0\" * n\n",
    "        visit = set([euler])\n",
    "        findpath = True\n",
    "        cf = 0\n",
    "        while findpath:\n",
    "            findpath = False\n",
    "            newcircle = []\n",
    "            for i in range(cf, len(euler) - n + 1):\n",
    "                #12\n",
    "                #10 back 12\n",
    "                cpass = euler[i:i + n]\n",
    "                link = cpass[:n-1]\n",
    "                for op in ops:\n",
    "                    if link + op not in visit:\n",
    "                        findpath = True\n",
    "                        newway = link + op\n",
    "                        visit.add(newway)\n",
    "                        newcircle.append(newway)\n",
    "                        cf = i\n",
    "                        break\n",
    "                if findpath:\n",
    "                    break\n",
    "            if findpath:\n",
    "                target = euler[cf:cf + n]\n",
    "                midcircle = \"\"\n",
    "                findtarget = False\n",
    "                while newcircle:\n",
    "                    current = newcircle.pop()\n",
    "                    link = current[-n + 1:]\n",
    "                    for op in ops:\n",
    "                        newpass = link + op\n",
    "                        if newpass == target:\n",
    "                            findtarget = True\n",
    "                            midcircle = current+op\n",
    "                            break\n",
    "                        if newpass not in visit and newpass not in current:\n",
    "                            newcircle.append(current + op)\n",
    "                    if findtarget:\n",
    "                        break\n",
    "                euler = euler[:cf] + midcircle + euler[cf + n:]\n",
    "                for j in range(len(midcircle) - n):\n",
    "                    visit.add(midcircle[j:j + n])\n",
    "        return euler\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
